import java.util.Arrays;
import java.util.PriorityQueue;

public class Review {

    /*public static void swap(int[] arr, int p, int q) {
        int t = arr[p];
        arr[p] = arr[q];
        arr[q] = t;
    }

    public static void partition(int[] arr, int k) {
        int less = -1,i = 0, more = arr.length;//less是小于边界  more是大于边界
        while (i < more) {
            if (arr[i] < k) {
                swap(arr, ++less, i++);//比给定数字小，与边界的下一个数字交换，边界扩张
            } else if (arr[i] > k){    //比给定数字大，与大于边界的下一个数字交换，大于边界扩张
                swap(arr, --more, i);
            } else {
                i++;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,2,4,3,2,7,3,4,1};
        partition(arr, 3);
        System.out.println(Arrays.toString(arr));
    }

     */

    /*public static void swap(int[] arr, int p, int q) {
        int t = arr[p];
        arr[p] = arr[q];
        arr[q] = t;
    }

    public static void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            swap(arr, l + (int) ((r - l + 1) * Math.random()), r);//取中间随机值
            int[] p = partition(arr, l, r);//分治取边界
            //边界取递归
            quickSort(arr, l, p[0] - 1);
            quickSort(arr, p[1] + 1, r);
        }
    }

    public static int[] partition(int[] arr, int l, int r) {
        int less = l - 1, more = r;//由于前面已经交换，所以此时r即使给定的partition数字
        //partition过程
        while (l < more) {
            if (arr[l] < arr[r]) {
                swap(arr,++less, l++);
            } else if (arr[l] > arr[r]) {
                swap(arr, --more, l);
            } else {
                l++;
            }
        }

        swap(arr, more, r);//partition完成后交换
        return new int[]{less + 1, more};//返回所求边界
    }

    public static void main(String[] args) {
        int[] arr = {2,6,1,4,3,7,10,8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

     */

    /*public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {//比自己父大，交换
            swap(arr, index, (index - 1 ) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void swap(int[] arr, int p, int q) {
        int t = arr[p];
        arr[p] = arr[q];
        arr[q] = t;
    }

    public static void heapify(int[] arr, int index, int heapSize) {
        int left = 2 * index + 1;//左孩子
        while (left < heapSize) {
            //左右孩子找最大值
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ?
                    left + 1 : left;
            //最大值与父亲比较
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = 2 * left + 1;
        }
    }


    public static void main(String[] args) {
        int[] arr = {2,1,4,3,5,7,6,8};
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        System.out.println(Arrays.toString(arr));//数组调整为大根堆
        arr[0] = 1;//修改根节点的值
        int heapSize = arr.length;//堆的大小
        heapify(arr, 0, heapSize);//heapify过程
        System.out.println(Arrays.toString(arr));
    }

     */

    /*public static void swap(int[] arr, int p, int q) {
        int t = arr[p];
        arr[p] = arr[q];
        arr[q] = t;
    }

    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {//比自己父大，交换
            swap(arr, index, (index - 1 ) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void heapify(int[] arr, int index, int heapSize) {
        int left = 2 * index + 1;//左孩子
        while (left < heapSize) {
            //左右孩子找最大值
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ?
                    left + 1 : left;
            //最大值与父亲比较
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = 2 * left + 1;
        }
    }

    public static void heapSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);//调整为大根堆
        }
        int heapSize = arr.length;
        swap(arr, 0, --heapSize);//最后一个元素交换
        while (heapSize > 0) {
            heapify(arr, 0, heapSize);//heapify过程
            swap(arr, 0, --heapSize);
        }
    }

    public static void main(String[] args) {
        int[] arr = {2,8,1,3,2,10,18,13,5};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

     */

    /*public static void main(String[] args) {
        int[] arr = {1,2,4,5,3,4,5,8,6,7,8,10};
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int k = 2;//假设k是2
        int l = 0, i = 0;
        for ( i = 0; i < k; i++) {
            heap.add(arr[i]);//前k个元素放入heap中
        }
        while (i < arr.length) {
            arr[l++] = heap.poll();//弹出一个加一个
            heap.add(arr[i++]);
        }
        while (!heap.isEmpty()) {
            arr[l++] = heap.poll();//最后全部弹出
        }
        System.out.println(Arrays.toString(arr));
    }

     */

    public static int maxDigit(int[] arr) {//获取数组中最大位数
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(max, arr[i]);
        }
        int res = 0;
        while (max != 0) {
            max /= 10;
            res++;
        }
        return res;
    }

    public static int getDigit(int num, int d) {//获取数组中元素的某个位置的数字
        return num / (int) (Math.pow(10, d)) % 10;
    }

    public static void radixSort(int[] arr, int l, int r, int digit) {
        final int radix = 10;//基数
        int[] bucket = new int[r - l + 1];//桶
        int i, j;
        for (int d = 1; d <= digit; d++) {//因为最大是digit位数，所以循环要进行digit次
            int[] count = new int[radix];//字典计数
            for (i = l; i <= r; i++) {
                j = getDigit(arr[i], d - 1);//把每一位放在count里面
                count[j]++;
            }
            for (i = 1; i < radix; i++) {
                count[i] += count[i - 1];//前缀和处理优化
            }
            for (i = r; i >= l; i--) {
                j = getDigit(arr[i], d - 1);
                bucket[count[j] - 1] = arr[i];//根据自己的位数的大小，逆序倒在桶里面
                count[j]--;
            }
            for (i = l, j = 0; i <= r; i++, j++) {//桶里面依次倒出
                arr[i] = bucket[j];
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {101, 25, 97, 33, 88, 56, 123, 4, 1, 441};
        radixSort(arr, 0, arr.length - 1, maxDigit(arr));
        System.out.println(Arrays.toString(arr));
    }
}